<html><head>
<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">

<title>Problem K: KTV</title>
<link rel="stylesheet" href="acm-11218_files/problem.html">
</head><body>

<center>
<h1>Problem K</h1>
<h2>KTV</h2>
</center>

<p>One song is extremely popular recently, so you and your friends decided to sing it in KTV. 
The song has 3 characters, so exactly 3 people should sing together each time (yes, there are 3 microphones in the room). 
There are exactly 9 people, so you decided that each person sings exactly once. In other words, all the people are divided into 
3 disjoint groups, so that every person is in exactly one group.</p>

<p align="center"><img src="acm-11218_files/p11218.png"></p>

<p>However, some people don't want to sing with some other people, and some combinations perform worse than others combinations. 
Given a score for every possible combination of 3 people, what is the largest possible score for all the 3 groups?</p>

<h2>Input</h2>
The input consists of at most 1000 test cases. Each case begins with a line containing a single integer <i>n</i> (0 &lt; <i>n</i> &lt; 81), 
the number of possible combinations. The next <i>n</i> lines each contains 4 positive integers <i>a</i>, <i>b</i>, <i>c</i>, <i>s</i> 
(1 &lt;= <i>a</i> &lt; <i>b</i> &lt; <i>c</i> &lt;= 9, 0 &lt; <i>s</i> &lt; 10000), that means a score of <i>s</i> is given to the combination (<i>a</i>,<i>b</i>,<i>c</i>). 
The last case is followed by a single zero, which should not be processed.

<h2>Output</h2>
For each test case, print the case number and the largest score. If it is impossible, print -1.

<h2>Sample Input</h2>
<pre>3
1 2 3 1
4 5 6 2
7 8 9 3
4
1 2 3 1
1 4 5 2
1 6 7 3
1 8 9 4
0
</pre>

<h2>Output for the Sample Input</h2>
<pre>Case 1: 6
Case 2: -1
</pre>

<hr>
<i>Rujia Liu's Present 2: A Big Contest of Brute Force</i><br>
</body></html>